package leetcode_字符串._12中心扩散法;

/**
 * 最长回文字串
 * 算法 :
 *   暴力解法，两重循环，以第一重循环的数为开始，加上后面的数后，是不是回文串
 *   动态规划，注意填表要从下往上填
 *     要理解在 [i, j] 中，如果 s[i] = s[j]，则需要看 [i + 1, j - 1] 是不是回文串
 */
public class _5最长回文串 {
    public static void main(String[] args) {
        System.out.println(new _5最长回文串().longestPalindrome_2("aaaa"));
    }

    public String longestPalindrome_1(String s) {
        if (s == null || s.length() == 1) {
            return s;
        }
        char[] tem = s.toCharArray();
        int maxLen = 1, begin = 0;
        for (int i = 0; i < tem.length - 1; i++) {
            for (int j = i + 1; j < tem.length; j++) {
                // 优化了一下，如果当前字符串长度小于最大回文串的长度，直接跳过
                if (j - i + 1 < maxLen) {
                    continue;
                }
                if (isPalindrome(tem, i, j)) {
                    if (maxLen < j - i + 1) {
                        maxLen = j - i + 1;
                        begin = i;
                    }
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }

    public String longestPalindrome_2(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        int begin = 0, maxLen = 1;
        char[] c = s.toCharArray();
        boolean[][] dp = new boolean[len][len];
        for (int i = len - 1; i >= 0; --i) {
            for (int j = i; j < len ; ++j) {
                if (j == i) {
                    dp[i][j] = true;
                    continue;
                }
                if (c[i] == c[j]) {
                    // 当 bb 这种情况时，要判断是不是相邻的
                    if (j == i + 1 || dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        if (maxLen < j - i + 1) {
                            maxLen = j - i + 1;
                            begin = i;
                        }
                    }
                }
            }
        }
        System.out.println(begin + " " + maxLen);
        return s.substring(begin, begin + maxLen);
    }

    public boolean isPalindrome(char[] c, int left, int right) {
        while (left < right) {
            if (c[left] != c[right]) {
                break;
            }
            ++left;
            --right;
        }
        return left >= right;
    }

}
